package arithmetic;

public class ChainTest {
    public static void main(String[] args) {
        int[] values1 = {5};
        int[] values2 = {5};
        ListNode head1 = createLinkedList(values1);
        ListNode head2 = createLinkedList(values2);
        addTwoNumbers(head1, head2);
    }

    /**
     * 这里是执行方法
     *
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == l2) {
            return l2;
        }
        if (l2 == null) {
            return l2;
        }
        // 同时遍历两个数组，当短的一个遍历完后，在单独遍历长的
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode dummy = new ListNode(0);
        ListNode p3 = dummy;
        // 是否往前进位
        boolean advance = false;
        while (p1 != null && p2 != null) {
            int v1 = p1.val;
            int v2 = p2.val;
            int v = v1 + v2;
            if (advance) {
                v += 1;
            }
            if (v >= 10) {
                advance = true;
                v = v - 10;
            } else {
                advance = false;
            }
            // 构造新的链表
            ListNode node = new ListNode(v);
            p3.next = node;
            p3 = node;
            // 遍历
            p1 = p1.next;
            p2 = p2.next;
        }
        // 把长的剩下部分接上
        if (p1 == null && p2 != null) {
            join(p2, advance, p3);
        } else if (p2 == null && p1 != null) {
            join(p1, advance, p3);
        } else if (p1 == null && p2 == null && advance) {
            continueAdvance(p3, 1);
        }
        return dummy.next;
    }

    // 把长的链表拼上去
    public static void join(ListNode node, boolean advance, ListNode p3) {
        while (node != null) {
            // 是否往前进位
            int v = node.val;
            if (advance) {
                v += 1;
            }
            if (v >= 10) {
                advance = true;
                v = v - 10;
            } else {
                advance = false;
            }
            // 构造节点
            ListNode newNode = new ListNode(v);
            p3.next = newNode;
            p3 = newNode;
            // 遍历
            node = node.next;
        }
        if (advance) {
            continueAdvance(p3, 1);
        }

    }

    // 边界处理，当所有的遍历结束，最后一次相加大于10，则还需要增加节点
    public static void continueAdvance(ListNode p3, int i) {
        ListNode newNode = new ListNode(i);
        p3.next = newNode;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode dummyHead = new ListNode();
        ListNode current = dummyHead;

        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }

        return dummyHead.next;
    }
}